package class06;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/sort-an-array/submissions/">912. 排序数组</a>
 */
public class Code03_HeapSort {
    // 大根堆可变数组数据结构
    public static class MyMaxHeap {

        private final ArrayList<Integer> heap;

        public MyMaxHeap() {
            this.heap = new ArrayList<>();
        }

        public void push(int value) {
            heap.add(value);
            heapInsert(heap.size() - 1);
        }

        public int peek() {
            return heap.get(0);
        }

        public int pop() {
            int result = heap.get(0);
            heap.set(0, heap.get(heap.size() - 1));
            heap.remove(heap.size() - 1);
            heapify(0);
            return result;
        }

        public boolean isEmpty() {
            return heap.size() == 0;
        }

        private void heapify(int index) {
            int left = (index << 1) + 1;
            while (left < heap.size()) {
                int maxIndex = left + 1 < heap.size() && heap.get(left + 1) > heap.get(left) ? left + 1 : left;
                maxIndex = heap.get(index) > heap.get(maxIndex) ? index : maxIndex;
                if (index == maxIndex) {
                    break;
                }
                swap(index, maxIndex);
                index = maxIndex;
                left = (index << 1) ^ 1;  // index * 2 + 1;
            }
        }

        private void heapInsert(int index) {
            while (heap.get(index) > heap.get((index - 1) / 2)) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void swap(int a, int b) {
            int t = heap.get(a);
            heap.set(a, heap.get(b));
            heap.set(b, t);
        }
    }

    public static void heapSort(int[] arr) {

        // // 从上向下建大根堆 O(N·log N)
        // for (int i = 0; i < arr.length; ++i) {
        //     heapInsert(arr, i);
        // }

        // 从下向上建大根堆 O(N)
        for (int i = arr.length - 1; i >= 0; --i) {
            heapify(arr, i, arr.length);
        }

        int heapSize = arr.length;
        while (heapSize > 0) {
            swap(arr, 0, --heapSize);
            heapify(arr, 0, heapSize);
        }
    }

    private static void heapInsert(int[] heap, int index) {
        // 末尾插入往上找，看看有没有比父节点小，有就交换，稳定指成为大顶堆
        while (heap[index] > heap[(index - 1) / 2]) {
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private static void heapify(int[] heap, int index, int heapSize) {
        int left = (index << 1) ^ 1;
        while (left < heapSize) {
            int maxIndex = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
            maxIndex = heap[index] > heap[maxIndex] ? index : maxIndex;
            if (maxIndex == index) {
                break;
            }
            swap(heap, index, maxIndex);
            index = maxIndex;
            left = (index << 1) ^ 1;  // index * 2 + 1
        }
    }

    private static void swap(int[] heap, int x, int y) {
        int t = heap[x];
        heap[x] = heap[y];
        heap[y] = t;
    }

    public static void main(String[] args) {
        for (int x = 0; x < 100; ++x) {
            int[] arr1 = new int[100];
            for (int i = 0; i < arr1.length; ++i) {
                arr1[i] = (int) (Math.random() * 100);
            }
            int[] arr2 = arr1.clone();
            heapSort(arr1);
            Arrays.sort(arr2);
            for (int i = 0; i < arr1.length; ++i) {
                if (arr1[i] != arr2[i]) {
                    System.out.println("错误");
                    break;
                }
            }
        }
    }

}
